//
// Created by liushuai on 2020/3/25.
//

#include "levelOrder.h"
vector<vector<int>> levelOrder(TreeNode* root)
{
    queue<TreeNode*> current;
    vector<vector<int>> result;
    if (root)
    {
        current.push(root);
        while (!current.empty())
        {
            int count = current.size();
            vector<int> layers;
            while (count)
            {
                TreeNode* node = current.front();
                current.pop();
                layers.push_back(node->val);
                if (node->left)
                    current.push(node->left);
                if (node->right)
                    current.push(node->right);
                count--;
            }
            if (layers.size() > 0)
                result.push_back(layers);
        }
    }
    return result;
}
void levelOrder1(TreeNode* root, int layer, std::vector<std::vector<int>>& result)
{
    if (root)
    {
        // 不能直接push_back，通过判断result的大小获取层数否则层result的size可能会大于层数
        if (result.size() < layer + 1)
            result.push_back(std::vector<int>());
        result.at(layer).push_back(root->val);
        levelOrder1(root->left, layer + 1, result);
        levelOrder1(root->right, layer + 1, result);
    }
}
std::vector<std::vector<int>> levelOrder1(TreeNode* root)
{
    std::vector<std::vector<int>> result;
    levelOrder1(root, 0, result);
    return result;
}
